'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-04-08 22:02:33
'''
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def tot(x, y):
            re = 0
            while x:
                re += x%10
                x = int(x/10)
            while y:
                re += y%10
                y = int(y/10)
            return re

        dire = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        test = [[False for _ in range(n)] for _ in range(m)]
        import queue
        store = queue.Queue()
        store.put((0, 0))
        test[0][0] = True
        re = 1
        while not store.empty():
            x, y = store.get()
            for tmp in dire:
                new_x = x + tmp[0]
                new_y = y + tmp[1]
                if tot(new_x, new_y) > k or new_x<0 or new_x>=m or new_y<0 or new_y>=n or test[new_x][new_y]:
                    continue
                test[new_x][new_y] = True
                print(new_x, new_y)
                re += 1
                store.put((new_x, new_y))
        return re

if __name__ == "__main__":
    so = Solution()
    print(so.movingCount(1, 2, 1))